package phase1.part2;

import java.io.FileNotFoundException;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

import phase1.part2.NFAFileReader.FileFormatException;

/**
 * A Converter converts an NFA to a DFA from being given only the starting NFA state and the alphabet of the language.
 * 
 * @author Devin Wang
 * @version Nov 13, 2012
 */
public class Converter  {
    
    private Set<String> stateNames;
    private Map<String, State> statesDFA;
    private State startDFA;
    private List<State> acceptingDFA;
    private Map<String, List<Transition>> transitionsDFA;
    
    private NFAFileReader reader;
	private State startNFA;
    
    private Map<String, List<State>> dfaTOnfa;
    
    /**
     * Create a converter. Take in the filepath of the input file of an NFA to create an NFAFileReader
     * that will extract all the necessary information. Get the information from the NFAFileReader,
     * then convert and minimize within the constructor.
     * @param filename The filepath of the input NFA file
     * @throws FileNotFoundException
     * @throws FileFormatException
     */
	public Converter(String filename) throws FileNotFoundException, FileFormatException {
        stateNames = new TreeSet<>();
		statesDFA = new HashMap<>();
		startDFA = null;
		acceptingDFA = new ArrayList<>();
		transitionsDFA = new HashMap<>();
        
        reader = new NFAFileReader(filename);
        startNFA = reader.getStart();
        dfaTOnfa = new HashMap<>();
        
        convert(startNFA, reader.getAlphabet());
        minimizeDFA();
	}
	
	/**
	 * Get the labels for all the states in the converted DFA.
	 * @return stateNames
	 */
	public Set<String> getStateNames(){
        return stateNames;
    }
    
	/**
	 * Get the start state in the DFA.
	 * @return startDFA
	 */
	public State getStartDFA(){
        return startDFA;
    }
    
	/**
	 * Get the accepting states in a DFA.
	 * @return acceptingDFA
	 */
	public List<State> getAcceptingDFA(){
        return acceptingDFA;
    }
    
	/**
	 * Get a map of all of the transitions in a DFA.
	 * @return transitionsDFA
	 */
	public Map<String, List<Transition>> getTransitionsDFA(){
        return transitionsDFA;
    }
	
	/**
	 * Convert the NFA to a DFA given the starting NFA state and the alphabet of the language.
	 * @param startNFA The starting NFA state
	 * @param alphabet The alphabet of the language
	 */
	private void convert(State startNFA, Set<Character> alphabet){
		List<State> statesEClosure = new ArrayList<>();
		statesEClosure.add(startNFA);
		
		startDFA = eClosure(statesEClosure);
		State currentDFA = startDFA;
		List<String> unmarkedDFAStates = new ArrayList<>();
        unmarkedDFAStates.add(startDFA.getLabel());
		List<String>markedDFAStates = new ArrayList<>();
		
		while(!unmarkedDFAStates.isEmpty()){
        	String currentDFALabel = unmarkedDFAStates.remove(0);
        	markedDFAStates.add(currentDFALabel);
            currentDFA = statesDFA.get(currentDFALabel);
            for (char c : alphabet){
            	State moveDFA = moveDFA(currentDFA, c);
                if(moveDFA != null){
                    boolean alreadyExists = currentDFA.updateTransitions(moveDFA, c);
                    if(!alreadyExists){
                        if(transitionsDFA.containsKey(currentDFALabel)){
                            transitionsDFA.get(currentDFALabel).add(currentDFA.findTransition(moveDFA));
                        }
                        else{
                            List<Transition> newList = new ArrayList<>();
                            newList.add(currentDFA.findTransition(moveDFA));
                            transitionsDFA.put(currentDFALabel, newList);
                        }
                    }
                    if((!unmarkedDFAStates.contains(moveDFA.getLabel())) && (!markedDFAStates.contains(moveDFA.getLabel()))){
                        unmarkedDFAStates.add(moveDFA.getLabel());
                    }
                }
            }
        }
	}
	
	/**
	 * Move on the DFA.
	 * @param currentDFA The current DFA state.
	 * @param c The character to move from
	 * @return the next state
	 */
	private State moveDFA(State currentDFA, char c){
		List<State> moveNFA = moveNFA(currentDFA, c);
		return eClosure(moveNFA);
	}
    
	/**
	 * Move on the NFA using the current DFA state's equivalent list of NFA states.
	 * @param currentDFA The current DFA state
	 * @param c The character to move from
	 * @return a list of all next NFA states
	 */
    private List<State> moveNFA(State currentDFA, char c){
        List<State> moveNFA = new ArrayList<>();
        for(State s : dfaTOnfa.get(currentDFA.getLabel())){
            for(Transition t : s.getTransitions()){
                if(t.accepts(c)){
                    if(!moveNFA.contains(t.getEnd())){
                        moveNFA.add(t.getEnd());
                    }
                }
            }
        }
        return moveNFA;
    }
	
    /**
     * Get the e-Closure DFA state of a list of NFA states.
     * @param states List of NFA states
     * @return the DFA state equivalent of the e-Closure
     */
    private State eClosure(List<State> states){
    	if(states.isEmpty()){
    		return null;
    	}
    	
    	List<State> toVisit = new ArrayList<>();
    	List<State> visited = new ArrayList<>();
    	
    	toVisit.addAll(states);
    	while(!toVisit.isEmpty()){
    		State s = toVisit.remove(0);
    		if(!visited.contains(s)){
    			visited.add(s);
    			for(Transition t : s.getTransitions()){
    				if(t.isETransition()){
    					toVisit.add(t.getEnd());
    				}
    			}
    		}
    	}
    	
    	for(State s : statesDFA.values()) {
            List<State> compareList = new ArrayList<>();
            compareList.addAll(dfaTOnfa.get(s.getLabel()));
            if(compareList.containsAll(visited) && visited.containsAll(compareList)){
            	return s;
            }
        }
    	
    	return createNewDFAState(visited);
    }
    
    /**
     * Create a new DFA state, determine whether or not it is accepting based on its equivalent list of NFA states,
     * add it to the DFA and to the labels set, and put it on the map with its NFA equivalent list.
     * @param nfaEquivalent The NFA equivalent list
     * @return a new DFA state
     */
    private State createNewDFAState(List<State> nfaEquivalent){
    	char c = (char)('A' + statesDFA.size());
    	String newLabel = Character.toString(c);
        State newDFAState = new State(Character.toString(c));
        
        for(State s : nfaEquivalent){
            if(s.getAccepting() && !newDFAState.getAccepting()){
                newDFAState.setAccepting(true);
                newDFAState.setTokenClass(s.getTokenClass());
                acceptingDFA.add(newDFAState);
            }
        }
        statesDFA.put(newLabel, newDFAState);
        stateNames.add(newLabel);
        dfaTOnfa.put(newLabel, nfaEquivalent);
        return newDFAState;
    }
    
    /**
     * Minimize the DFA until it can no longer be minimalized.
     */
    private void minimizeDFA(){
    	Partition pOld = new Partition(stateNames,acceptingDFA);
    	Partition pNew = minimizeHandler(pOld);
    	
    	while(!pNew.equals(pOld)){
    		pOld = pNew;
    		pNew = minimizeHandler(pOld);
    	}
    }
    
    /**
     * Minimize the DFA and then repartition its states.
     * @param pOld The old partition
     * @return the new partition to be compared against the old to determine if the DFA has been minimized.
     */
    private Partition minimizeHandler(Partition pOld){
    	List<String> accepting = pOld.getAccepting();
    	List<String> nonAccepting = pOld.getNonAccepting();
    	List<State> removeList = new ArrayList<>();
    	Map<String, State> redirectMap = new HashMap<>();
    	
    	findEquivalents(accepting, removeList, redirectMap);
    	findEquivalents(nonAccepting, removeList, redirectMap);
    	
    	Set<String> keys = redirectMap.keySet();
    	for(String s : keys){
    		transitionRedirect(statesDFA.get(s),redirectMap.get(s), removeList);
    	}
    	
    	remove(removeList);
    	
    	return new Partition(stateNames, acceptingDFA);
    }
    
    /**
     * Find all duplicate states.
     * @param stateSet The set of states to search
     * @param removeList The list to add duplicate states to be removed to
     * @param redirectMap The map to add duplicate states to be redirected to their original states on all transitions pointing to them
     */
    private void findEquivalents(List<String> stateSet, List<State> removeList, Map<String, State> redirectMap){
    	for(int i = 0; i < stateSet.size()-1; i++){
    		State a = statesDFA.get(stateSet.get(i));
    		for(int j = i+1; j < stateSet.size(); j++){
    			State b = statesDFA.get(stateSet.get(j));
    			if(!stateSet.contains(a)){
    				if(compare(a,b)){
        				if(!removeList.contains(b)){
        					redirectMap.put(b.getLabel(),a);
        					removeList.add(b);
        				}
        			}
    			}
    		}
    	}
    }
   
    /**
     * Check if two states are duplicates.
     * @param a One of the two states
     * @param b The other of the two states
     * @return <CODE>true</CODE> if the two states share the same transitions, <CODE>false</CODE> if not
     */
    private boolean compare(State a, State b){
    	for(Transition t1 : a.getTransitions()){
    		Transition t2 = b.findTransition(t1.getEnd());
    		if(t2 != null){
    			if(!t1.getPattern().equals(t2.getPattern())){
    				return false;
    			}
    		}
    		else return false;
    	}
    	for(Transition t1 : b.getTransitions()){
    		Transition t2 = a.findTransition(t1.getEnd());
    		if(t2 != null){
    			if(!t1.getPattern().equals(t2.getPattern())){
    				return false;
    			}
    		}
    		else return false;
    	}
    	return true;
    }
    
    /**
     * Redirect all transitions pointing to a duplicate state to its original state.
     * @param oldEnd The old end state
     * @param newEnd The new end state
     * @param removeList The list of duplicate states being removed. Don't bother redirecting any transitions from states that are going to be removed
     */
    private void transitionRedirect(State oldEnd, State newEnd, List<State> removeList){
    	for (String s : stateNames){
    		if(!removeList.contains(statesDFA.get(s))){
    			for(Transition t : transitionsDFA.get(s)){
    				if(t.getEnd().equals(oldEnd)){
    					t.setEnd(newEnd);
    				}
    			}
    		}
    	}
    }
    
    /**
     * Remove all duplicate states, update all necessary Collections.
     * @param removeList The list of states to remove from the DFA
     */
    private void remove(List<State> removeList){
    	for(State s : removeList){
    		stateNames.remove(s.getLabel());
    		statesDFA.remove(s.getLabel());
    		acceptingDFA.remove(s);
    		transitionsDFA.remove(s.getLabel());
    	}
    	
    	Set<String> oldNames = new TreeSet<>();
    	oldNames.addAll(stateNames);
    	
    	int count = 0;
    	for(String oldName : oldNames){
    		String newName = Character.toString((char)('A' + count));
    		if(!oldName.equals(newName)){
    			State s = statesDFA.remove(oldName);
    			s.setLabel(newName);
    			statesDFA.put(newName, s);
    			stateNames.remove(oldName);
    			stateNames.add(newName);
    			List<Transition> trans = transitionsDFA.remove(oldName);
    			transitionsDFA.put(newName, trans);
    		}
    		count++;
    	}
    }
}